//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：matrix = [], target = 0
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 0 <= m, n <= 100 
// -104 <= matrix[i][j], target <= 104 
// 
// Related Topics 数组 二分查找 
// 👍 266 👎 0


package com.yun.leetcode.editor.cn;

public class SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrix().new Solution();
        int[][] matrix = {
                {1},{3},{5}
        };
        System.out.println(solution.searchMatrix(matrix, 4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix.length == 0) {
                return false;
            }
            int m = matrix.length;
            int n = matrix[0].length;
            // 二分查找，多行串联是一个有序的数组。取中值需要认真计算；
            int leftX = 0;
            int leftY = 0;
            int rightX = m - 1;
            int rightY = n - 1;
            while (isLeft(leftX, leftY, rightX, rightY)) {
                // ERROR: 这样算中间数的话，有问题，eg：[0,0][1,0] -> mid[0,0]
//                int midX = (leftX + rightX) / 2;
//                int midY = (leftY + rightY) / 2;
                // 想法是算距离吧，然后用left的位置去加
                int posLeft = leftX * n + leftY;
                int posRight = rightX * n + rightY;
                int offset = (posRight - posLeft) / 2;
                int midX = leftX + offset / (n);
                int midY = leftY + offset % (n);
                if (midY > n - 1) {
                    midY = 0;
                    if (midX == m - 1) {
                        return false;
                    }
                    midX = midX +1;
                }
                if (target > matrix[midX][midY]) {
                    leftX = midX;
                    leftY = midY + 1;
                    if (leftY > n - 1) {
                        if (leftX == m - 1) {
                            return false;
                        } else {
                            leftX += 1;
                            leftY = 0;
                        }
                    }
                } else if (target < matrix[midX][midY]) {
                    rightX = midX;
                    rightY = midY - 1;
                    if (rightY < 0) {
                        if (rightX == 0) {
                            return false;
                        } else {
                            rightY = n - 1;
                            rightX = rightX - 1;
                        }
                    }
                } else {
                    return true;
                }
            }
            return false;
        }


        public boolean isLeft(int leftX, int leftY, int rightX, int rightY) {
            if (leftX < rightX) {
                return true;
            }
            if (leftX == rightX) {
                return leftY <= rightY;
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}